package prastice;

import java.util.*;

public class TopKFrequent {
    public List<String> topKFrequent(String[] words, int k) {
        // 1. 先统计 word 的个数
        HashMap<String, Integer> map = new HashMap<>();
        for(String word : words) {
            if(map.get(word) == null) {
                map.put(word, 1);
            } else {
                map.put(word, map.get(word) + 1);
            }
        }

        // 2. 进行排序
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                // 频率相同排字典
                int compare = o1.getValue().compareTo(o2.getValue());
                return compare != 0 ? compare : -o1.getKey().compareTo(o2.getKey()) ;
            }
        });
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                // 直接加 所以给 minHeap 传入比较器的时候就要判断 频率与字典
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> peek = minHeap.peek();
                int compare = entry.getValue().compareTo(peek.getValue());
                if(compare > 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if(compare == 0 && entry.getKey().compareTo(peek.getKey()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }
        }

        // 3. 获取 key
        List<String> list = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            list.add(0, minHeap.poll().getKey());
//            list.add(minHeap.poll().getKey());
        }
//        // 4. 反转
//        Collections.reverse(list);
        return list;
    }
}
